package stack_queue.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wenjingyuan
 * @Date: 2022/09/26/20:03
 * @Description:杨辉三角
 * https://leetcode.cn/problems/pascals-triangle/
 */
public class Num118 {
    public List<List<Integer>> generate(int numRows) {
        //二维数组retList
        List<List<Integer>> retList=new ArrayList<>();
        //组装最简单的第一行和第二行
        List<Integer> first=new ArrayList<>();
        first.add(1);
        retList.add(first);
        if(numRows==1){
            return retList;
        }
        //第二行
        List<Integer> second=new ArrayList<>();
        second.add(1);
        second.add(1);
        retList.add(second);
        if(numRows==2){
            return retList;
        }
        //此时一定是大于等于三行的
        for(int i=3;i<=numRows;i++){
            //[i,j]=[i-1,j-1]+[i-1,j]
            //取得当前行的前一行元素
            List<Integer> prev=retList.get(i-1-1);
            //准备组合本行元素
            List<Integer> cur=new ArrayList<>();
            cur.add(1);
            for(int j=2;j<i;j++){
                //[i,j]=[i-1,j-1]+[i-1,j]
                int temValue=prev.get(j-1-1)+prev.get(j-1);
                cur.add(temValue);
            }
            cur.add(1);
            retList.add(cur);
        }
        return retList;
    }
}
